package main

import (
	"container/list"
	"fmt"
	"math"
	"tree"
)

func main() {
	list := tree.BuildList(989, nil, 10250, 98693, -89388, nil, nil, nil, -32127)
	root := tree.BuildTree(list)
	fmt.Println(maxLevelSum(root))
}

func maxLevelSum(root *tree.TreeNode) int {
	q := list.New()
	if root == nil {
		return 0
	}
	q.PushBack(root)
	level := 0
	maxLevel := 0
	maxSum := math.MinInt32
	for q.Len() > 0 {
		size := q.Len() //记录每一层的节点数
		level++
		sum := 0
		for i := 0; i < size; i++ {
			node := q.Remove(q.Front()).(*tree.TreeNode)
			sum += node.Val
			//fmt.Println(node.Val, " sum=", sum)
			if node.Left != nil {
				q.PushBack(node.Left)
			}
			if node.Right != nil {
				q.PushBack(node.Right)
			}

		}
		if sum > maxSum {
			maxSum = sum
			maxLevel = level
			//fmt.Println(maxLevel, maxSum)
		}
		//fmt.Println()
	}
	return maxLevel
}
